//https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/?envType=daily-question&envId=2023-12-07


class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        typedef pair<int, int> PII;
        vector<vector<PII>> g(n); // 第一个存边, 第二个存正向还是反向
        for (auto&c : connections) {
            int u = c[0], v = c[1];
            g[u].push_back(PII(v, 1));
            g[v].push_back(PII(u, -1));
        }
        int cnt = 0;
        function<void(int, int)> dfs = [&](int x, int fa) {
            for (auto [y, dir] : g[x]) {
                if (y != fa) {
                    if (dir == 1) cnt += 1;
                    dfs(y, x);
                }
            }
        };
        dfs(0, -1);
        return cnt;
    }
};